#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define SUCCESS 1
#define FAILURE 0
#define OK 2
#define OUTOFINDEX 0
#define TRUE 3
#define FALSE -3
#define ERROR 0

typedef int Status;
typedef char ElemSet;

//*****************双向链表类型*******************
typedef struct LNode{
	ElemSet data;
	struct LNode *prior;
	struct LNode *next;
}LNode,*LinkList;

typedef struct LNode2{
	struct LNode *head,*tail;	
} *DLinkList;


LinkList getTail(LinkList l) {
	struct LNode *p=l;
	if (p==NULL) return NULL;
	while (p->next!=NULL) p=p->next;
	return p;
}
Status InitList(LinkList* LN,ElemSet* str,int len){
	*LN=(LinkList)malloc(sizeof(LNode));
	if(*LN==NULL) return FAILURE;
	if(str==NULL || len==0) return OK;
	LinkList p,r=(*LN);
	r->prior=r->next=NULL;
	int i=0;
	if(str[0]=='-')i=1;
	while(i++<len){
		p=(LinkList)malloc(sizeof(LNode));
		if(p==NULL) return FAILURE;
		p->data=str[i-1]-'0';
		p->next=r->next,r->next=p,p->prior=r,r=p;
	}
	return SUCCESS;
}

Status DestoryList(LinkList L){
	LinkList p=L->next;
	while(p!=NULL) {
		free(L);
		L=p;
		p=p->next;
	}
	free(L);
	return SUCCESS;
}

Status ClearList(LinkList L){
	if(L->next==NULL) return OK;
	LinkList p=L->next,r=p->next;
	while(r!=NULL){
		free(p);
		p=r;
		r=r->next;
	}
	free(p);
	L->next=NULL;
	return SUCCESS;
}

Status ListEmpty(LinkList L){
	if(L->next==NULL) return TRUE;
	return FALSE;
}

int ListLength(LinkList L){
	int len=0;
	LinkList p=L->next;
	while(p!=NULL){
		len++;
		p=p->next;
	}
	return len;
} 

Status GetElem(LinkList L,int i,ElemSet* e){
	if(i<1) {*e=98;return OUTOFINDEX;}
	LinkList p=L->next;
	int counter=1;
	while(p!=NULL && counter++<i){
		p=p->next;
	}
	if(p==NULL) return OUTOFINDEX;
	*e=p->data;
	return SUCCESS;
}

int LocatElem(LinkList L,ElemSet e,int (*FUNC)(LinkList L,ElemSet e)){
	int index=(*FUNC)(L,e);
	if(index) return index;
	return ERROR;
}

Status PriorElem(LinkList L,ElemSet cur_e,ElemSet* e){
	LinkList r,p=L->next;
	r=p->next;
	while(r!=NULL){
		if(r->data==cur_e) return p->data;
		p=r;
		r=r->next;
	}
	return ERROR;
}

Status NextElem(LinkList L,ElemSet cur_e,ElemSet* e){
	LinkList r,p=L->next;
	r=p->next;
	while(r!=NULL){
		if(p->data==cur_e) return r->data;
		p=r;
		r=r->next;
	}
	return ERROR;
}

Status ListInsert(LinkList L,int i,ElemSet e){

	LinkList r=NULL,p=L,q=NULL;
	int index=1;
	while(p!=NULL && index++<i){
		p=p->next;
	}
	if(p==NULL || index>i && index==1) return FAILURE;
	r=(LinkList)malloc(sizeof(LNode));
	if (r==NULL) printf("!!!!!!\n");
	r->data=e;
	r->next=NULL;
	if (p==NULL) printf("p=NULL\n");
	if((q=p->next)!=NULL)q->prior=r;
	r->next=p->next;
	p->next=r;
	r->prior=p;
	return SUCCESS;
}

Status ListDelete(LinkList L,int i,ElemSet* e){
	LinkList r,p=L->next;
	if(i==1) {
		L->next=p->next;
		free(p);
		return SUCCESS;
	}
	int j=1;
	while(p!=NULL && ++j<i){
		p=p->next;
	}
	if(p==NULL || j>i) return FAILURE;
	r=p->next;
	p->next=r->next;
	r->next->prior=r->prior;
	*e=r->data;
	free(r);
	return SUCCESS;
	
}

Status ListTravese(LinkList L,int (*FUNC)(LinkList L,ElemSet e)){
	LinkList p=L->next;
	while(p!=NULL){
		if(!(*FUNC)(L,p->data)) return FAILURE;
		p=p->next;
	}
	return SUCCESS;

}

Status ToString(LinkList L,char* str){
	LinkList p=L->next;
	if(p==NULL || p->next==NULL) return FAILURE;
	while(p!=NULL){
		sprintf(str++,"%d",p->data);
		p=p->next;
	}
	return SUCCESS;
}


//对链表元素进行排序，L为头指针，ch为排序选择，非负为升序，负数为降序；
Status sort(LinkList L,int ch){
	LinkList r,p=L->next;
	ElemSet e;
	p=L->next,r=p->next;

	if(ch>=0){
		while(p->next!=NULL){
			while(r!=NULL){
				if(p->data > r->data) {
					e=p->data;
					p->data=r->data;
					r->data=e;
				}
				r=r->next;
			}
			p=p->next;
			r=p->next;
		}
		return SUCCESS;
	}
	else while(p->next!=NULL){
			while(r!=NULL){
				if(p->data < r->data) {
					e=p->data;
					p->data=r->data;
					r->data=e;
				}
				r=r->next;
			}
			p=p->next;
			r=p->next;
		}
		return SUCCESS;

}

//合并两个链表到第三个新的链表里
Status merger(LinkList la,LinkList lb,LinkList* lc){
	*lc=(LinkList)malloc(sizeof(LNode));
	(*lc)->next=NULL;
	LinkList pa=la->next;
	LinkList pb=lb->next;
	LinkList pc=*lc;

	while(pa!=NULL && pb!=NULL){
		if(pa->data < pb->data){
		 pc->next=pa;
		 pc=pa;
		 pa=pa->next;
		}
		else{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}

	}
    if(pa==NULL) pc->next=pb;
    else pc->next=pa;
    la->next=NULL;
    lb->next=NULL;

	
	return SUCCESS;
}

int getlen(char* str){
	return strlen(str);
}

int compearList(LinkList la,LinkList lb){
	LinkList p=la->next;
	LinkList q=lb->next;
	int len1=ListLength(la);
	int len2=ListLength(lb);
	int sign;
	if(len1!=len2){
		len1>len2 ? sign=1:sign=-1;
		return sign;
	}
	while(p!=NULL && q!=NULL){
		if(p->data!=q->data)p->data>q->data?sign=1:sign=-1;
		p=p->next;
		q=q->next;
	}
	if(p==NULL && q==NULL) sign=0;
	return sign;
}

Status FillList(LinkList L,ElemSet* str,int len){
	if(L->next!=NULL) ClearList(L);
	LinkList p,r=L;
	r->prior=r->next=NULL;
	int i=0;
	if(str[0]=='-')i=1;
	while(len-->i){
		p=(LinkList)malloc(sizeof(LNode));
		if(p==NULL) return FAILURE;
		p->data=str[len];
		p->next=r->next,r->next=p,p->prior=r,r=p;
	}
	return SUCCESS;
}